UVa/843 - Crypt kicker/843.comentarios.cpp

   1 #include <sstream>
   2 #include <iostream>
   3 #include <map>
   4 #include <string>
   5 #include <vector>
   6 #include <set>
   7
   8 using namespace std;
   9
  10 //Los diferentes diccionarios clasificados según la longitud de las cadenas que contienen:
  11 map<int, set<string> > dict;
  12 //Ej: dict[4] me da un set de strings que contiene todas las palabras dadas en el diccionario de longitud 4
  13
  14
  15 //El mapeo ideal para una solución. Es decir, solucion['a'] == 'b' si cada 'a' que aparece en la línea la tengo que
  16 //que reemplazar por una 'b' en la salida.
  17 map<char, char> solucion;
  18 //La declaro como una variable global porque la necesito en varias funciones.
  19
  20
  21 //Retorna verdadero si al intentar mapear todos los caracteres del parámetro <origen> a todos los caracteres de
  22 //<destino> se produce una contradicción o un mapeo ilegal.
  23 //El último parámetro <crypt> contiene un mapeo de las palabras que se han visto hasta el momento de llamar
  24 //esta función. Notar que el parámetro <crypt> se pasa por copia y no por referencia (Porque no tiene &).
  25 //Esto lo hago porque <crypt> se modifica dentro de la función, y no me sirve que al llamar la función quede
  26 //modificado afuera, entonces hago una copia que puedo modificar libremente sin riesgos.
  27 bool contradice(const string &origen, const string &destino,  map<char, char> crypt){
  28   if (origen.length() != destino.length()) return true;
  29
  30   for (int i=0; i<origen.size(); ++i){
  31     if (crypt.count(origen[i]) == 1){
  32       if (crypt[origen[i]] != destino[i]){ //Caso 1: Ya había asignado esta letra a otra diferente
  33         return true;
  34       }
  35     }else{
  36       for (map<char, char>::iterator j = crypt.begin(); j != crypt.end(); ++j){
  37         if ((*j).second == destino[i]) return true; //Caso 2: Ya existía otra letra diferente en <origen> a la que le
  38       }                                             //        habían asignado la misma letra
  39       crypt[origen[i]] = destino[i];
  40     }
  41   }
  42   return false;
  43 }
  44
  45
  46 //Realiza una asignación de todas las letras de <origen> a todas las de <destino>.
  47 //Nuevamente notar que <crypt> es una copia.
  48 map<char, char> asignar(const string &origen, const string &destino, map<char, char> crypt){
  49   if (origen.size() == destino.size()){
  50     for (int i=0; i<origen.size(); ++i){
  51       crypt[origen[i]] = destino[i];
  52     }
  53   }
  54   return crypt;
  55 }
  56
  57 //Esta función es la más importante del programa, es la que se encarga de realizar la fuerza bruta.
  58 //Los parámetros son:
  59 //i -> la posición en el vector <words> que estamos intentando desencriptar
  60 //words -> un vector con todas las palabras que queremos desencriptar
  61 //crypt -> El mapeo de letras que hemos encontrado hasta ahora. Este parámetro se puede modificar
  62 //libremente dentro de la función porque es una copia.
  63
  64 //Retorna verdadero si logra desencriptar <words> o falso si no.
  65 bool backtrack(const int &i, const vector<string> &words, map<char, char> crypt){
  66   //Si estoy intentado desencriptar una palabra FUERA del vector, es porque encontré una solución.
  67   if (i >= words.size()){
  68     solucion = crypt;
  69     return true;
  70   }
  71
  72   int len = words[i].length();
  73   set<string> possible = dict[len];
  74
  75   //Vamos a intentar todas las posibles opciones de desencriptación (?) de esta palabra.
  76   //Sabemos que tienen que ser de la misma longitud, así que en <possible> metemos el set de
  77   //palabras posibles de la misma longitud que aparecen en el diccionario
  78   for (set<string>::iterator j = possible.begin(); j != possible.end(); ++j){ //Para cada posible palabra...
  79     if (!contradice(words[i], (*j), crypt)){ //Si es una contradicción entonces sigue con la próxima palabra
  80       if (backtrack(i+1, words, asignar(words[i], (*j), crypt))){ //Sino, el éxito de la asignación
  81                                                                   //que hemos visto hasta ahora
  82         return true;                                              //depende del éxito que tengamos
  83                                                                   //al continuar la "rama del árbol"
  84       }
  85
  86     }
  87
  88   }
  89   return false; //Si llegamos hasta acá es porque ya evaluamos todas las posibles opciones y ninguna tuvo éxito.
  90 }
  91
  92 int main(){
  93   int n;
  94   cin >> n;
  95   while (n--){
  96     string s;
  97     cin >> s;
  98     dict[s.length()].insert(s); //Clasifica las palabras según su longitud
  99   }
 100   getchar(); //Lee un dummy '\n'
 101   string line;
 102   while (getline(cin, line)){
 103
 104     if (line == ""){
 105       cout << "\n";
 106       continue;
 107     }
 108
 109     //Esta parte mete en <words> todas las palabras separadas. Utilizo un stringstream para hacer el split.
 110     vector<string> words;
 111     stringstream ss(line);
 112     string word;
 113     while (ss >> word){
 114       words.push_back(word);
 115     }
 116
 117     //Si encuentro solución empezando en la primera palabra y empezando con un mapeo vacío...
 118     if (backtrack(0, words, map<char, char>() )){
 119       for (int i=0; i<line.size(); ++i){
 120         if (line[i] == ' ') cout << " ";
 121         else cout << solucion[line[i]]; //Imprimo la solución
 122       }
 123       cout << endl;
 124     }else{
 125       for (int i=0; i<line.size(); ++i){
 126         if (line[i] == ' ') cout << " ";
 127         else cout << "*"; //Imprimo la no solución
 128       }
 129       cout << endl;
 130     }
 131   }
 132   return 0;
 133 }